package com.gzzz.sort;


import java.util.ArrayList;
import java.util.Comparator;

public class HeapSortString {

    public static ArrayList<String> sort(ArrayList<String> inputList) {
        int n = inputList.size();

        // 构建堆（重新排列数组）
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(inputList, n, i, String.CASE_INSENSITIVE_ORDER);
        }

        // 逐个从堆中提取元素
        for (int i = n - 1; i > 0; i--) {
            // 将当前根节点移到末尾
            String temp = inputList.get(0);
            inputList.set(0, inputList.get(i));
            inputList.set(i, temp);

            // 在减小的堆上调用最大堆化
            heapify(inputList, i, 0, String.CASE_INSENSITIVE_ORDER);
        }

        return inputList;
    }

    // 用于最大堆化子树的方法，根节点为索引i，数组大小为n
    private static void heapify(ArrayList<String> inputList, int n, int i, Comparator<String> comparator) {
        int largest = i;  // 将最大值初始化为根节点
        int leftChild = 2 * i + 1;
        int rightChild = 2 * i + 2;

        // 如果左子节点大于根节点
        if (leftChild < n && comparator.compare(inputList.get(leftChild), inputList.get(largest)) > 0) {
            largest = leftChild;
        }

        // 如果右子节点大于到目前为止的最大值
        if (rightChild < n && comparator.compare(inputList.get(rightChild), inputList.get(largest)) > 0) {
            largest = rightChild;
        }

        // 如果最大值不是根节点
        if (largest != i) {
            String swap = inputList.get(i);
            inputList.set(i, inputList.get(largest));
            inputList.set(largest, swap);

            // 递归地在受影响的子树上进行最大堆化
            heapify(inputList, n, largest, comparator);
        }
    }

    public static void main(String[] args) {
        ArrayList<String> inputList = new ArrayList<>();
        inputList.add("banana");
        inputList.add("apple");
        inputList.add("orange");
        inputList.add("grape");
        inputList.add("Pear");
        inputList.add("Cherry");

        System.out.println("未排序的列表: " + inputList);

        ArrayList<String> sortedList = sort(inputList);

        System.out.println("排序后的列表: " + sortedList);
    }
}
